#include "../tools.h"

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word2.size() + 1, vector<int>(word1.size() + 1, -1));
        for(int i = 0; i < word1.size() + 1; ++i)
            dp[word2.size()][i] = word1.size() - i;
        for(int i = 0; i < word2.size() + 1; ++i)
            dp[i][word1.size()] = word2.size() - i;
        // show(dp);

        for(int i = word1.size() - 1; i > -1; --i){
            for(int j = word2.size() - 1; j > -1; --j){
                if(word1[i] == word2[j]){
                    dp[j][i] = dp[j + 1][i + 1];
                }else{
                    dp[j][i] = min(1 + dp[j + 1][i], min(1 + dp[j][i + 1], 1 + dp[j + 1][i + 1]));
                }
            }
        }
        // show(dp);

        return dp[0][0];
    }
};

int main(int argc, char const *argv[])
{
    string word1 = "horse", word2 = "ros";
    Solution s;
    cout << s.minDistance(word1, word2);




    return 0;
}
